home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / D-G / GemsI / Original / BitInterleaving.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-16  |  6.3 KB  |  170 lines  |  [TEXT/MPS ]
  1. /*
  2. Bit Interleaving for Quad- or Octrees
  3. by Clifford A. Shaffer
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include "GraphicsGems.h"
  8. #define B_MAX_DEPTH 14    /* maximum depth allowed */
  9.  
  10. /* byteval is the lookup table for coordinate interleaving.  Given a
  11.    4 bit portion of the (x, y) coordinates, return the bit interleaving.
  12.    Notice that this table looks like the order in which the pixels of
  13.    a 16 X 16 pixel image would be visited. */
  14. int byteval[16][16] = 
  15.     {  0,  1,  4,  5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85,
  16.        2,  3,  6,  7, 18, 19, 22, 23, 66, 67, 70, 71, 82, 83, 86, 87,
  17.        8,  9, 12, 13, 24, 25, 28, 29, 72, 73, 76, 77, 88, 89, 92, 93,
  18.       10, 11, 14, 15, 26, 27, 30, 31, 74, 75, 78, 79, 90, 91, 94, 95,
  19.       32, 33, 36, 37, 48, 49, 52, 53, 96, 97,100,101,112,113,116,117,
  20.       34, 35, 38, 39, 50, 51, 54, 55, 98, 99,102,103,114,115,118,119,
  21.       40, 41, 44, 45, 56, 57, 60, 61,104,105,108,109,120,121,124,125,
  22.       42, 43, 46, 47, 58, 59, 62, 63,106,107,110,111,122,123,126,127,
  23.      128,129,132,133,144,145,148,149,192,193,196,197,208,209,212,213,
  24.      130,131,134,135,146,147,150,151,194,195,198,199,210,211,214,215,
  25.      136,137,140,141,152,153,156,157,200,201,204,205,216,217,220,221,
  26.      138,139,142,143,154,155,158,159,202,203,206,207,218,219,222,223,
  27.      160,161,164,165,176,177,180,181,224,225,228,229,240,241,244,245,
  28.      162,163,166,167,178,179,182,183,226,227,230,231,242,243,246,247,
  29.      168,169,172,173,184,185,188,189,232,233,236,237,248,249,252,253,
  30.      170,171,174,175,186,187,190,191,234,235,238,239,250,251,254,255};
  31.  
  32. /* bytemask is the mask for byte interleaving - masks out the 
  33.    non-significant bit positions.  This is determined by the
  34.    depth of the node. For example, a node of depth 0 is at the root.
  35.   Thus, there are no branchs and no bits are significant. 
  36.   The bottom 4 bits (the depth) are always retained. 
  37.   Values are in octal notation. */
  38. int bytemask[B_MAX_DEPTH + 1] = {017,
  39.      030000000017,036000000017,037400000017,037700000017,
  40.      037760000017,037774000017,037777000017,037777600017,
  41.      037777740017,037777770017,037777776017,037777777417,
  42.      037777777717,037777777777};
  43.  
  44.  
  45. long *interleave(addr, x, y, depth, max_depth)
  46. /* Return the interleaved code for a quadtree node at depth depth 
  47. whose upper left hand corner has coordinates (x, y) in a tree with maximum depth max_depth.  This function receives and returns a 
  48. pointer to addr, which is either a long interger or (more typically)
  49. an array of long integers whose first integer contains the 
  50. interleaved code. */
  51.  long *addr;
  52.  int max_depth, depth;
  53.  int x, y;
  54. {
  55.  
  56. /* Scale x, y values to be consistent with maximum coord size */
  57. /* and depth of tree */
  58.  x <<= (B_MAX_DEPTH - max_depth);
  59.  y <<= (B_MAX_DEPTH - max_depth);
  60.  
  61. /* calculate the bit interleaving of the x, y values that have now
  62.    been appropriately shifted, and place this interleave in the address
  63.    portion of addr.  Note that the binary representations of x and y are
  64.    being processed from right to left */
  65.  
  66.  *addr = depth;
  67.  *addr |= byteval[y & 03][x & 03] << 4;
  68.  *addr |= byteval[(y >> 2) & 017][(x >> 2) & 017] << 8;
  69.  *addr |= byteval[(y >> 6) & 017][(x >> 6) & 017] << 16;
  70.  *addr |= byteval[(y >> 10) & 017][(x >> 10) & 017] << 24;
  71.  *addr &= bytemask[depth];
  72.  
  73. /* if there were unused portions of the x and y addresses then  */
  74. /* the address was too large for the depth values given.  */
  75. /*  Return address built */
  76.  return (addr);
  77. }
  78.  
  79.  
  80.  
  81. /* The next two arrays are used in calculating the (x, y) coordinates
  82.    of the upper left-hand corner of a node from its bit interleaved
  83.    address.  Given an 8 bit number, the arrays return the effect of
  84.    removing every other bit (the y bits preceed the x bits). */
  85.  
  86. int xval[256] = { 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  87.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  88.                  0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  89.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  90.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  91.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15,
  92.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  93.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15,
  94.                  0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  95.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  96.                  0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
  97.                  4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
  98.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  99.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15,
  100.                  8, 9, 8, 9,10,11,10,11, 8, 9, 8, 9,10,11,10,11,
  101.                 12,13,12,13,14,15,14,15,12,13,12,13,14,15,14,15};
  102.  
  103.  
  104. int yval[256] = { 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  105.               0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  106.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  107.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  108.               0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  109.               0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
  110.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  111.               4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
  112.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  113.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  114.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15,
  115.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15,
  116.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  117.               8, 8, 9, 9, 8, 8, 9, 9,10,10,11,11,10,10,11,11,
  118.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15,
  119.              12,12,13,13,12,12,13,13,14,14,15,15,14,14,15,15};
  120.  
  121.  
  122.  
  123.  
  124.  
  125. int getx(addr, max_depth)
  126. /* Return the x coordinate of the upper left hand corner of addr for a
  127.    tree with maximum depth max_depth. */
  128.  long *addr;
  129.  int max_depth;
  130. {
  131.  register x;
  132.  
  133.  x = xval[(*addr >> 4) & 017];
  134.  x |= xval[(*addr >> 8) & 0377] << 2;
  135.  x |= xval[(*addr >> 16) & 0377] << 6;
  136.  x |= xval[(*addr >> 24) & 0377] << 10;
  137.  x >>= B_MAX_DEPTH - max_depth;
  138.  return (x);
  139. }
  140.  
  141.  
  142.  
  143. int QKy(addr, max_depth)
  144. /* Return the y coordinate of the upper left hand corner of addr for a
  145.    tree with maximum depth max_depth. */
  146.  
  147.  long *addr;
  148.  int max_depth;
  149. {
  150.  register y;
  151.  
  152.  y = yval[(*addr >> 4) & 017];
  153.  y |= yval[(*addr >> 8) & 0377] << 2;
  154.  y |= yval[(*addr >> 16) & 0377] << 6;
  155.  y |= yval[(*addr >> 24) & 0377] << 10;
  156.  y >>= B_MAX_DEPTH - max_depth;
  157.  return (y);
  158. }
  159.  
  160. int getdepth(addr)
  161. /* Return the depth of the node.  Simply return the bottom 4 bits. */
  162.  
  163.  long *addr;
  164. {
  165.  
  166.  return(*addr & 017);
  167. }
  168.  
  169.  
  170.